Complex Event Processing (CEP) is a method of tracking and analyzing streams of information from multiple data sources about things that happen and identifying an event or pattern of events from them. CEP systems have been designed to support complex event detection queries. Recently, applications such as radio-frequency identification (RFID), healthcare, multi-tenant stock monitoring and data center monitoring are emerging, wherein event stream data are being shared among users and many concurrent pattern queries are being submitted. For example, users may be interested in different patterns of stock trade events from New York Stock Exchange (NYSE). Those patterns often partially overlap with each other and the stream data (stock trade events) is commonly shared by users.
Sub-expression sharing has been proposed as a basic technique for sharing common computation among pattern queries. The essence of this sharing technique is that pattern queries can simply merge their common prefix, infix or suffix state in order to avoid duplicate computation. Nevertheless, these existing studies rely on heuristics, such as longest prefix sharing, which can lead to a sub-optimal execution plan for the whole query set.